/**
 * 
 */
package hihocoder;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

/**
 * @author zhongfang
 *
 */
public class 区间统计 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int mod=1000000007;
		Scanner scanner=new Scanner(System.in);
		int T=scanner.nextInt();
		while (T-->0) {
			int N=scanner.nextInt();
			int M=scanner.nextInt();
			int A[]=new int[N];
//			int B[][]=new int[N][N];//詞頻統計
			for (int i = 0; i < N; i++) {
				A[i]=scanner.nextInt();
			}
			for (int i = 0; i < M; i++) {
				int L=scanner.nextInt()-1;
				int R=scanner.nextInt()-1;
				int K=scanner.nextInt();
				HashMap<Integer, Integer> freq=new HashMap<>();
				for (int j = L; j <= R; j++) {
					if(freq.containsKey(A[j])){
						freq.put(A[j], freq.get(A[j])+1);
					}else {
						freq.put(A[j], 1);
					}
				}
				int result=0;
				HashMap<Integer, Integer> res=new HashMap<>();
				for (int j : freq.values()) {
					result=(result+(int)getPower(j,K,mod,res))%mod;
				}
				System.out.println(result);
			}
		}
	}

	private static long getPower(int j, int k, int mod, HashMap<Integer, Integer> res) {
		if(res.containsKey(j)){
			return res.get(j);
		}
		if(k==1){
			return j;
		}
		long half=getPower(j, k/2, mod, res);
		long tmp=half*half%mod;
		if(k%2==1){
			tmp=tmp*j%mod;
		}
		return tmp;
	}

}
